package middle;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import util.PrintUtils;

public class Solution_399 {

    private Map<String, Set<String>> map;
    private Map<String, Double> valueMap;
    private Set<String> exists;

    public double[] calcEquation(List<List<String>> equations, double[] values, List<List<String>> queries) {
        map = new HashMap<>();
        valueMap = new HashMap<>();
        exists = new HashSet<>();
        Set<String> all = new HashSet<>();
        for (int i = 0; i < equations.size(); i++) {
            List<String> strings = equations.get(i);
            all.add(strings.get(0));
            all.add(strings.get(1));

            Set<String> set = map.getOrDefault(strings.get(0), new HashSet<>());
            set.add(strings.get(1));
            map.put(strings.get(0), set);
            valueMap.put(strings.get(0) + "-" + strings.get(1), values[i]);

            Set<String> set1 = map.getOrDefault(strings.get(1), new HashSet<>());
            set1.add(strings.get(0));
            map.put(strings.get(1), set1);
            valueMap.put(strings.get(1) + "-" + strings.get(0), 1 / values[i]);
        }

        double[] rst = new double[queries.size()];
        for (int i = 0; i < queries.size(); i++) {
            double dps = -1.0;
            if (all.contains(queries.get(i).get(0)) && all.contains(queries.get(i).get(1))) {
                exists.clear();
                dps = dps(queries.get(i).get(0), queries.get(i).get(1));
                if (dps < 0) {
                    dps = dps(queries.get(i).get(1), queries.get(i).get(0));
                    dps = 1.0 / dps;
                }
            }
            rst[i] = dps;
        }
        return rst;
    }

    private double dps(String head, String last) {
        if (head.equals(last)) {
            return 1.0;
        } else if (exists.contains(head)) {
            return -1.0;
        }
        Set<String> strings = map.get(head);
        if (strings == null) {
            return -1.0;
        }
        exists.add(head);
        for (String string : strings) {
            double dps = dps(string, last);
            if (dps >= 0) {
                return valueMap.get(head + "-" + string) * dps;
            }
        }
        exists.remove(head);
        return -1.0;
    }

    public static void main(String[] args) {
        Solution_399 model = new Solution_399();
        List<List<String>> equations = new ArrayList<>();
        equations.add(PrintUtils.newArrayList("a", "e"));
        equations.add(PrintUtils.newArrayList("b", "e"));

        double[] values = new double[]{4.0, 3.0};

        List<List<String>> queries = new ArrayList<>();
        queries.add(PrintUtils.newArrayList("a", "b"));
        queries.add(PrintUtils.newArrayList("e", "e"));
        queries.add(PrintUtils.newArrayList("x", "x"));

        System.out.println(Arrays.toString(model.calcEquation(equations, values, queries)));;
    }
}
